
function InvertColor(color)
{
	if (color === 0)
	{
		// throw new Error('InvertColor: Inverting 0');
		return 0;
	}
	var BasePair = 3;
	while ((BasePair & color) === 0) BasePair <<= 2;
	return color ^ BasePair;
}

// =============== Start of ColorNode Definitions ================ //
// class for coloring, represent either a cell or a candidate
function ColoringNode (row, col, value)
{
	this.r = row;
	this.c = col;
	this.b = CalcBoxNum(row, col);
	this.v = value;
	this.id = row * 100 + col * 10 + value.bitmaskToDigit();

	this.bilocalRow = false;
	this.bilocalCol = false;
	this.bilocalBox = false;
	this.bivalue = false;

	this.color = 0; // color of current cell, zero for non-conjugates
	this.colorInfluence = 0; // colors with influence on the current cell, meaning if any of those colors are TRUE, this cell be FALSE

	this.toString = function () { return '\n' + this.v.bitmaskToDigit() + '@' +  '(' + this.r + ',' + this.c + ')' + this.b + ' Color ' + this.color.toString(2) + ' peered ' + this.colorInfluence.toString(2); };
}

ColoringNode.prototype.isConjugate = function ()
{
	return this.bilocalRow || this.bilocalCol || this.bilocalBox || this.bivalue;
}

// Check if two cells to see if influence mark should be made.
ColoringNode.prototype.isPeer = function (y)
{
	if (this.v === y.v)
		return (this.r === y.r) || (this.c === y.c) || (this.b === y.b); 
	else
		return (this.r === y.r) && (this.c === y.c); 
}

// check two cells to see if they should be marked inverse colors. 
ColoringNode.prototype.isLocked = function (y)
{
	if (this.v === y.v)
		return (this.bilocalRow && this.r === y.r) || (this.bilocalCol && this.c === y.c) || (this.bilocalBox && this.b === y.b); 
	else
		return this.bivalue && this.r === y.r && this.c === y.c;
}

// =============== End of ColorNode Definitions ================ //
// =============== Start of ColorTree Definitions ================ //

// class for coloring, the entire coloring tree
function ColoringTree()
{
	this.row = [[], [], [], [], [], [], [], [], []];
	this.col = [[], [], [], [], [], [], [], [], []];
	this.box = [[], [], [], [], [], [], [], [], []];
	this.all = [];

	this.add = function (row, col, value)
	{
		var obj = new ColoringNode(row, col, value);
		this.row[row].push(obj);
		this.col[col].push(obj);
		this.box[obj.b].push(obj);
		this.all.push(obj);
		
		return obj;
	}
}

// start from one cell recursively color all related cells on the table
// related meaning bivalue or bilocal
ColoringTree.prototype.propagateColor = function (CurrCell, color0, color1)
{
	CurrCell.color |= color0;

	// loop thru row look for prospective cells to color
	for (var i = 0, len = this.row[CurrCell.r].length; i < len; i++)
	{
		// ignore current cell
		if (CurrCell.id === this.row[CurrCell.r][i].id) continue;

		// ignore non-influenced cells
		if (!CurrCell.isPeer(this.row[CurrCell.r][i])) continue;

		this.row[CurrCell.r][i].colorInfluence |= color0;

		// ignore colored cells
		if (this.row[CurrCell.r][i].color !== 0) continue;

		// check if prospective cell is a conjugate with the current cell, if it is recursively color it.
		if (CurrCell.isLocked(this.row[CurrCell.r][i]))
		{
			this.propagateColor(this.row[CurrCell.r][i], color1, color0);
		}
	}

	// loop thru col look for prospective cells to color
	for (var i = 0, len = this.col[CurrCell.c].length; i < len; i++)
	{
		// ignore current cell
		if (CurrCell.id === this.col[CurrCell.c][i].id) continue;

		// ignore non-influenced cells
		if (!CurrCell.isPeer(this.col[CurrCell.c][i])) continue;

		this.col[CurrCell.c][i].colorInfluence |= color0;

		// ignore colored cells
		if (this.col[CurrCell.c][i].color !== 0) continue;

		// check if prospective cell is a conjugate with the current cell, if it is recursively color it.
		if (CurrCell.isLocked(this.col[CurrCell.c][i]))
		{
			this.propagateColor(this.col[CurrCell.c][i], color1, color0);
		}
	}

	// loop thru box look for prospective cells to color
	for (var i = 0, len = this.box[CurrCell.b].length; i < len; i++)
	{
		// ignore current cell
		if (CurrCell.id === this.box[CurrCell.b][i].id) continue;

		// ignore non-influenced cells
		if (!CurrCell.isPeer(this.box[CurrCell.b][i])) continue;

		this.box[CurrCell.b][i].colorInfluence |= color0;

		// ignore colored cells
		if (this.box[CurrCell.b][i].color !== 0) continue;

		// check if prospective cell is a conjugate with the current cell, if it is recursively color it.
		if (CurrCell.isLocked(this.box[CurrCell.b][i]))
		{
			this.propagateColor(this.box[CurrCell.b][i], color1, color0);
		}
	}
}

// loop ColoringTree_PropagateColor thru all eligible cells.
ColoringTree.prototype.colorAllCells = function ()
{
	var BaseColor = 1;

	// Color conjugate cells, and mark influence
	for (var i = 0, len = this.all.length; i < len; i++)
	{
		if (this.all[i].color === 0 && this.all[i].isConjugate())
		{
			this.propagateColor(this.all[i], BaseColor, BaseColor << 1);
			BaseColor <<= 2;
		}

		// we can only use 15 color pairs [2^(2*15)], any number larger than this will cause one of the colors to override the sign bit.
		// altho we can use the sign bit, it will make debugging difficult as the binary print out would be unreadable.
		if (BaseColor >= 1073741824) break; 
	}
}

// After a coloring operation is complete, this function applies any removed candidates back to the sudoku grid. 
ColoringTree.prototype.enforceColors = function (grid)
{
	var InvalidColorPairs = [];
	for (var i = 0, ilen = this.all.length; i < ilen; i++)
	{
		if (this.all[i].color === 0) continue;

		var CurrentInverse = InvertColor(this.all[i].color);
		var InfluencedColors = this.all[i].colorInfluence.splitBinary();

		// PrintLog('(' + this.all[i].r + ',' + this.all[i].c + ') colored ' + this.all[i].color.toString(2) + ' is influenced by ' + this.all[i].colorInfluence.toString(2));
		for (var j = 0, jlen = InfluencedColors.length; j < jlen; j++)
			InvalidColorPairs.push(CurrentInverse | InvertColor(InfluencedColors[j]));
	}
	InvalidColorPairs.sort();

	var last, changed = false;
	for (var j = 0, jlen = InvalidColorPairs.length; j < jlen; j++)
	{
		if (last === InvalidColorPairs[j]) continue;
		last = InvalidColorPairs[j];

		for (var i = 0, ilen = this.all.length; i < ilen; i++)
		{
			if ((this.all[i].colorInfluence & last) === last)
			{
				var row = this.all[i].r;
				var col = this.all[i].c;
				// console.log('#' + this.all[i].v.bitmaskToDigit() + '@(' + row + ',' + col + ') peered bad colors, p:' + this.all[i].colorInfluence.toString(2) + ',s:' + last.toString(2));
				grid.setNotation (row, col, grid.notations[row][col] & ~this.all[i].v);
				changed = true;
			}
		}
	}

	return changed;
}



// =============== End of ColorTree Definitions ================ //

// Method: 
// 1) Compile a list of all unfilled cells containing a given candidate. 
// 2) Color all conjugate cells in this list using the coloring method.
// NOTE: Each chain contain 2 color, alternating at each conjugate. Each color represents a set of candidates that must be true or false all at once. 
//       Removal of any single candidate in the chain cause the chain to be solved, solution being cells of the inverse color. 
// 4) Compute the Influence colors on every cell (both conjugates and non-conjugates). Influence colors are other colors that appears in the peer list.

// Rules: 
// 1) If a color contradicts itself (i.e. contain its own color in Influence), then it is invalid. 
//    Its inverse color must be TRUE, although this will be enforced in the next Hidden Singles run.
// 2) Any cell that peers with two cells of the same chain but opposing colors is invalid. 
//    This also applies to a conjugate of another chain
//    A simple single candidate removal is suffice, as next Singles run would resolve the chain.
// 3) For each conjugate, if any of its Influence color is TRUE, then its own color must be FALSE. Likewise, if itself is TRUE, then its Influence colors must FALSE.
//    It is not a lock because they can both be FALSE. However, we can conclude that of their two inverses, one must be TRUE. 
// NOTE: (1) is a special case of (2).
//       (2) is a special case of (3).
// If any of the 3 rules invalidates a conjugate, and the conjugate color could still be applied to other cells, it would simply validate the inverse in the process. 
SudokuGrid.prototype.strategyMultiColoring_Digit = function (value)
{
	// create a table of all cells with this candidate value
	var ColoringTable = new ColoringTree();

	// tally of number of this candidate in each row, col, row;
	var RowTally = [0, 0, 0, 0, 0, 0, 0, 0, 0]; 
	var ColTally = [0, 0, 0, 0, 0, 0, 0, 0, 0]; 
	var BoxTally = [0, 0, 0, 0, 0, 0, 0, 0, 0];

	for (var r = 0; r < 9; r++)
		for (var c = 0; c < 9; c++)
			if (this.isEmpty(r, c) && (this.notations[r][c] & value))
			{
				var ColorCell = ColoringTable.add(r, c, value);

				RowTally[r]++;
				ColTally[c]++;
				BoxTally[ColorCell.b]++;
			}

	var ConjugateCount = 0;
	
	// mark all cells that is part of a conjugate pair
	for (var i = 0, len = ColoringTable.all.length; i < len; i++)
	{
		if (RowTally[ColoringTable.all[i].r] === 2) ColoringTable.all[i].bilocalRow = true;
		if (ColTally[ColoringTable.all[i].c] === 2) ColoringTable.all[i].bilocalCol = true;
		if (BoxTally[ColoringTable.all[i].b] === 2) ColoringTable.all[i].bilocalBox = true;

		if (ColoringTable.all[i].isConjugate()) ConjugateCount++;
	}

	// we need at least 3 conjugates to form a useful chain
	if (ConjugateCount < 3) return false;

	//console.log('Conjugate Count for ' + value.bitmaskToDigit() + ': ' + ConjugateCount + ' out of ' + ColoringTable.all.length);

	ColoringTable.colorAllCells();
	return ColoringTable.enforceColors(this);
}

SudokuGrid.prototype.strategyMultiColoring = function ()
{
	console.log('=== Coloring ===');

	var changed = false;
	for (var i = 1; i < 512; i <<= 1)
	{
		// only returns success (1) or noavail (0).
		changed |= this.strategyMultiColoring_Digit(i);
	}
	return changed;
}

// The implementation of this function is very similar to the coloring (multi-coloring) strategy above. 
// Difference between this and multicoloring is that multicoloring only deals with one digit, while 3d medusa deals with all digits.
SudokuGrid.prototype.strategy3DMedusa = function ()
{
	console.log('=== 3D Medusa ===');
	var ColoringTable = new ColoringTree();

	// compile a list of candidates to color just like regular coloring strategy. 
	var candidates, ColoringObject;
	var ConjugateCount = 0;

	var RowTally = [], ColTally = [], BoxTally = [];

	for (var i = 0; i < 9; i++)
	{
		RowTally[i] = [0, 0, 0, 0, 0, 0, 0, 0, 0]; 
		ColTally[i] = [0, 0, 0, 0, 0, 0, 0, 0, 0]; 
		BoxTally[i] = [0, 0, 0, 0, 0, 0, 0, 0, 0];
	}

	for (var r = 0; r < 9; r++)
	{
		for (var c = 0; c < 9; c++)
		{
			candidates = this.notations[r][c].splitBinary();
			if (candidates.length === 1) continue; // ignore singles
			if (candidates.length === 0) throw new Error('Cell (' + r + ', ' + c + ') has no valid candidates.');

			for (var i = 0, len = candidates.length; i < len; i++)
			{
				ColoringObject = ColoringTable.add(r, c, candidates[i]);

				if (this.getPositionsInRow(candidates[i], r).bitCount() === 2) ColoringObject.bilocalRow = true;
				if (this.getPositionsInCol(candidates[i], c).bitCount() === 2) ColoringObject.bilocalCol = true;
				if (this.getPositionsInBox(candidates[i], ColoringObject.b).bitCount() === 2) ColoringObject.bilocalBox = true;
				if (candidates.length === 2) ColoringObject.bivalue = true;

				if (ColoringObject.isConjugate()) ConjugateCount++;
			}
		}
	}

	// we need at least 4 conjugates to form a useful chain
	if (ConjugateCount < 4) return false;

	//console.log('Conjugate Count for ' + value.bitmaskToDigit() + ': ' + ConjugateCount + ' out of ' + ColoringTable.all.length);

	ColoringTable.colorAllCells();
	return ColoringTable.enforceColors(this);
}
